//Given an array A of positive integers, A[i] represents the value of the i-th s
//ightseeing spot, and two sightseeing spots i and j have distance j - i between t
//hem. 
//
// The score of a pair (i < j) of sightseeing spots is (A[i] + A[j] + i - j) : t
//he sum of the values of the sightseeing spots, minus the distance between them. 
//
//
// Return the maximum score of a pair of sightseeing spots. 
//
// 
//
// Example 1: 
//
// 
//Input: [8,1,5,2,6]
//Output: 11
//Explanation: i = 0, j = 2, A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11
// 
//
// 
//
// Note: 
//
// 
// 2 <= A.length <= 50000 
// 1 <= A[i] <= 1000 
// Related Topics 数组


//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    fun maxScoreSightseeingPair(A: IntArray): Int {
        var result = 0
        var maxi = A[0]
        for (i in 1 until A.size) {
            result = Math.max(result, maxi + A[i] - i)
            maxi = Math.max(maxi, A[i] + i)
        }

        return result
    }
}
//leetcode submit region end(Prohibit modification and deletion)
